'''
线段树
区间 add
区间 update
区间 query 查询最大值
'''
import random
from typing import List


class SegmentTree:
    def __init__(self, nums: List[int]):
        self.n = n = len(nums)
        # sum info 数组
        self.info = [0] * (n << 2)
        # lazy add 数组
        self.lazy_add = [0] * (n << 2)
        # lazy update数组， update[i] 表示该节点的区间是否要重制，change[i]表示该节点区间修改成什么
        self.lazy_update = [False] * (n << 2)
        self.lazy_change = [0] * (n << 2)
        self._build(nums)

    def _build(self, nums):
        def f(l, r, root):
            if l == r:
                self.info[root] = nums[l - 1]
            else:
                mid = (l + r) >> 1
                f(l, mid, root << 1)
                f(mid + 1, r, root << 1 | 1)
                self._up(root)

        f(1, self.n, 1)  # 区间[1, n], root节点1

    def _up(self, root):
        self.info[root] = max(self.info[root << 1], self.info[root << 1 | 1])

    def _down(self, l, r, root):
        mid = (l + r) >> 1
        # 1) 父节点一定是最新的信息。
        # 2）父节点如果既有update 又有 add, 则一定是先update后add，因为update会清空add
        if self.lazy_update[root]:
            self._lazy_update(l, mid, root << 1, self.lazy_change[root])
            self._lazy_update(mid + 1, r, root << 1 | 1, self.lazy_change[root])
        if self.lazy_add[root]:
            self._lazy_add(l, mid, root << 1, self.lazy_add[root])
            self._lazy_add(mid + 1, r, root << 1 | 1, self.lazy_add[root])
        self.lazy_add[root] = 0
        self.lazy_update[root] = False

    def _lazy_add(self, l, r, root, v):
        self.info[root] += v
        self.lazy_add[root] += v

    def _lazy_update(self, l, r, root, v):
        self.info[root] = v
        self.lazy_update[root] = True
        self.lazy_change[root] = v
        self.lazy_add[root] = 0  # !!! 重置任务，会清空之前的累加信息

    def add(self, L, R, V):
        def f(l, r, root):
            if r < L or l > R: return  # 没这个区间的事情
            if L <= l and r <= R:  # 如果任务区间，包含了当前区间。直接懒更新
                self._lazy_add(l, r, root, V)
                return
            # 包含了一部分当前区间，那只能下发了。懒更新内容要下发
            self._down(l, r, root)
            mid = (l + r) >> 1
            f(l, mid, root << 1)
            f(mid + 1, r, root << 1 | 1)
            # 子节点更新完毕了，要更新当前节点的值
            self._up(root)

        f(1, self.n, 1)

    def update(self, L, R, V):
        def f(l, r, root):
            if r < L or l > R: return  # 没这个区间的事情
            if L <= l and r <= R:  # 如果任务区间，包含了当前区间。直接蓝更新
                self._lazy_update(l, r, root, V)
                return
            # 包含了一部分当前区间，那只能下发了。懒更新内容要下发
            self._down(l, r, root)
            mid = (l + r) >> 1
            f(l, mid, root << 1)
            f(mid + 1, r, root << 1 | 1)
            # 子节点更新完毕了，要更新当前节点的值
            self._up(root)

        f(1, self.n, 1)

    def query(self, L, R):
        def f(l, r, root):
            if r < L or l > R: return 0
            if L <= l and r <= R:
                return self.info[root]
            # 包含了一部分当前区间，还要往下分别收集，且要考虑懒更新内容
            self._down(l, r, root)
            mid = (l + r) >> 1
            return max(f(l, mid, root << 1), f(mid + 1, r, root << 1 | 1))

        return f(1, self.n, 1)


class Right:
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.nums = nums

    def query(self, L, R):
        nums = self.nums
        return max(nums[L - 1: R])

    def add(self, L, R, V):
        nums = self.nums
        for i in range(L - 1, R):
            nums[i] += V

    def update(self, L, R, V):
        nums = self.nums
        for i in range(L - 1, R):
            nums[i] = V


def test(t_operations=10000, n=1000):
    c1 = Right([0] * (n + 1))
    c2 = SegmentTree([0] * (n + 1))
    for _ in range(t_operations):
        op = random.randint(0, 2)
        L, R = random.randint(1, n), random.randint(1, n)
        L, R = min(L, R), max(L, R)
        V = random.randint(0, 100)
        if op == 0:
            if not c1.query(L, R) == c2.query(L, R):
                print('oops')
                break
        elif op == 1:
            c1.add(L, R, V)
            c2.add(L, R, V)
        else:
            c1.update(L, R, V)
            c2.update(L, R, V)
    print("done")


if __name__ == '__main__':
    test(n=10000)
